\section{Diffusion under adversarial dynamics}
\label{sec:intro.token}

In an adversarial dynamic network, nodes and communication links can
appear and disappear at will over time. Emerging networking
technologies such as ad hoc, wireless, sensor, mobile, and
peer-to-peer networks are inherently dynamic, resource-constrained,
and unreliable. This necessitates the development of a solid
foundation to design efficient, robust, and scalable algorithms for
diffusion processes in adversarial networks, and to understand the
power and limitation of distributed computing on such networks. Such a
foundation is critical to realize the full potential of these
large-scale dynamic communication networks.

As a step towards understanding the fundamental computation power of
such dynamic networks, we investigate dynamic networks in which the
network topology changes arbitrarily from round to round. We first
consider a worst-case model that was introduced by Kuhn, Lynch, and
Oshman~\cite{kuhn+lo:dynamic} in which the communication links for
each round are chosen by an online adversary, and nodes do not know
who their neighbors for the current round are before they broadcast
their messages. (Note that in this model, only edges change and nodes
are assumed to be fixed.) The only constraint on the adversary is that
the networks should be connected at each round. Unlike prior models on
dynamic networks, the model of \cite{kuhn+lo:dynamic} does not assume
that the network eventually stops changing and requires that the
algorithms work correctly and terminate even in networks that change
continually over time.

We study a fundamental diffusion process, information spreading (also
known as gossip) in such dynamic network. In gossip, or more
generally, $k$-gossip, there are $k$ pieces of information (or tokens)
that are initially present in some nodes and the problem is to
disseminate the $k$ tokens to all nodes. By just gossip, we mean
$n$-gossip, where $n$ is the network size. Information spreading is a
fundamental primitive in networks which can be used to solve other
problems such as leader election.

%\subsection{Our results}

The focus of this thesis is on the power of {\em token-forwarding}
algorithms, which do not manipulate tokens in any way other than
storing and forwarding them.  Token-forwarding algorithms are simple,
often easy to implement, and typically incur low overhead.  In a key
result,~\cite{kuhn+lo:dynamic} showed that under their adversarial
model, $k$-gossip can be solved by token-forwarding in $O(nk)$ rounds,
but that any deterministic online token-forwarding algorithm needs
$\Omega(n \log k)$ rounds.  They also proved an $\Omega(nk)$ lower
bound for a special class of token-forwarding algorithms, called
knowledge-based algorithms.  Our main result is a new lower bound on
{\em any} deterministic online token-forwarding algorithm for
$k$-gossip.
\begin{itemize}
\item
We show that every deterministic online token-forwarding algorithm for
the $k$-gossip problem takes $\Omega(nk/\log n)$ rounds. Our result
applies even to centralized (deterministic) token-forwarding
algorithms that have a global knowledge of the token distribution.
\end{itemize}
This result resolves an open problem raised in~\cite{kuhn+lo:dynamic},
significantly improving their lower bound, and matching their upper
bound to within a logarithmic factor.  Our lower bound also enables a
better comparison of token-forwarding with an alternative approach
based on network coding due to
~\cite{haeupler:gossip,haeupler+k:dynamic}, which achieves a
$O(nk/\log n)$ rounds using $O(\log n)$-bit messages (which is not
significantly better than the $O(nk)$ bound using token-forwarding),
and $O(n + k)$ rounds with large message sizes (e.g., $\Theta(n \log
n)$ bits). It therefore follows that for large token and message sizes
there is a factor $\Omega(\min\{n,k\}/\log n)$ gap between
token-forwarding and network coding. We note that in our model we
allow only one token per edge per round and thus our bounds hold
regardless of the token size.

Our lower bound indicates that one cannot obtain efficient (i.e.,
subquadratic) token-forwarding algorithms for gossip in the
adversarial model of~\cite{kuhn+lo:dynamic}.  Furthermore, for
arbitrary token sizes, we do not know of any algorithm that is
significantly faster than quadratic time.  This motivates considering
other weaker (and perhaps, more realistic) models of dynamic networks.
In fact, it is not clear whether one can solve the problem
significantly faster even in an offline setting, in which the network
can change arbitrarily each round, but the entire evolution is known
to the algorithm in advance.  Our next contribution takes a step in
resolving this basic question for token-forwarding algorithms.
\begin{itemize}
\item
We present a polynomial-time offline token-forwarding algorithm that
solves the $k$-gossip problem on an $n$-node dynamic network in
$O(\min\{nk, n^{1.5} \sqrt{\log n}\})$ rounds.
\item
We also present a polynomial-time offline token-forwarding algorithm
that solves the $k$-gossip problem in a number of rounds within an
$O(n^\epsilon)$ factor of the optimal, for any $\epsilon > 0$,
assuming the algorithm is allowed to transmit $O(\log n)$ tokens per
round.
\end{itemize}
The above upper bounds show that in the offline setting,
token-forwarding algorithms can achieve a time bound that is within
$O(\sqrt{n\log n})$ of the information-theoretic lower bound of
$\Omega(n + k)$, and that we can approximate the best token-forwarding
algorithm to within a $O(n^\epsilon)$ factor, given logarithmic extra
bandwidth per edge.
